package leetcode.all;

public class Solution1103 {
    public static void main(String[] args) {
        distributeCandies(1000000000,1000);
    }
    public static int[] distributeCandies(int candies, int num_people) {
        /**
         * 先计算足够发多少轮
         * 第一轮：n*(n+1)/2 + 0*n*n
         * 第二轮：n*(n+1)/2 + 1*n*n
         * 第m轮：n*(n+1)/2 + (m-1)*n*n
         */
        long candy = (long) candies;
        int m = (int) (Math.sqrt(8*candy+1)-1)/(2*num_people);
        //计算剩余多少糖果
        int tmp = m*(m-1)/2;
        int left = candies - num_people*(num_people+1)/2*m - tmp*num_people*num_people;
        //初始化返回值
        int[] res = new int[num_people];
        for (int i = 0; i < num_people; i++) {
            res[i] = m*(i+1)+num_people*tmp;
        }
        //分剩余的
        int base = m*num_people+1;//剩余的分给第一个小朋友的
        for (int i = 0; i < num_people; i++) {
            int alloc = Math.min(base,left);
            res[i] += alloc;
            left -= alloc;
            base++;
            if(left==0) break;
        }
        return res;
    }
}
